#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

struct ListNode 
{
    int val;
    struct ListNode* next;
};


//方法一
struct ListNode* partition(struct ListNode* head, int x) {
    if (head == NULL || head->next == NULL)
        return head;
    struct ListNode* cur = head;
    struct ListNode* newhead1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* newhead2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    newhead1->next = NULL;
    newhead2->next = NULL;
    struct ListNode* tail1, * tail2;
    tail1 = tail2 = NULL;
    while (cur)
    {
        if (cur->val < x)
        {
            if (tail1 == NULL)
            {
                newhead1->next = cur;
                tail1 = cur;
            }
            else
            {
                tail1->next = cur;
                tail1 = cur;
            }
        }
        else// cur->val >= x
        {
            if (tail2 == NULL)
            {
                newhead2->next = cur;
                tail2 = cur;
            }
            else
            {
                 tail2->next = cur;
                tail2 = cur;
            }
        }
        cur = cur->next;
    }
    if(tail2)
        tail2->next = NULL;
    if (newhead1->next == NULL)
    {
        return newhead2->next;
    }
    tail1->next = newhead2->next;
    struct ListNode* list = newhead1->next;
    free(newhead1);
    free(newhead2);
    return list;
}


//方法二
struct ListNode* partition(struct ListNode* pHead, int x)
{
    struct ListNode* lessHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* greaterHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* lessTail = lessHead;
    struct ListNode* greaterTail = greaterHead;
    lessTail->next = NULL;
    greaterTail->next = NULL;
    struct ListNode* cur = pHead;
    while (cur) {
        if (cur->val < x) {
            lessTail->next = cur;
            lessTail = lessTail->next;
        }
        else {
            greaterTail->next = cur;
            greaterTail = greaterTail->next;
        }
        cur = cur->next;
    }
    lessTail->next = greaterHead->next;
    greaterTail->next = NULL;
    struct ListNode* list = lessHead->next;
    free(lessHead);
    free(greaterHead);
    return list;
}